package chordrouting;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Endstart
 * Date: 2020-09-07
 * Time: 22:24
 */
public class ChordRouting {

    private static int SPACE_SIZE = 9;
    private static List<Integer> NODE_VALUE_LIST;
    static {
        NODE_VALUE_LIST = new ArrayList<>(Arrays.asList(0, 85, 133, 182, 210, 245, 279, 324, 395, 451));
    }

    private int spaceSize;
    private List<Node> nodeList;

    public static void main(String[] args) {
        String studentNumber = "s3478345";
        if (args != null && args.length == 1) {
            studentNumber = args[0];
        }
        int lastStudentNumber = Integer.parseInt(studentNumber.substring(studentNumber.length() - 1));

        ChordRouting chordRouting = new ChordRouting();
        chordRouting.init(SPACE_SIZE, NODE_VALUE_LIST);

        System.out.println("===================================================");
        System.out.println("Student number: " + studentNumber);
        System.out.println("Search key: k" + chordRouting.genKey(lastStudentNumber));
        System.out.println("Start node: " + chordRouting.getStartNode(lastStudentNumber).getNodeName());

        System.out.println("------------------------------------");
        Node node = chordRouting.search(lastStudentNumber);
        System.out.println("-------------------------------------");

        System.out.println("Search result: " + node.getNodeName());
        System.out.println("===================================================");

//        for (int i = 0; i < 10; i++) {
//            chordrouting.Node node = chordRouting.search(i);
//            System.out.println("search key: " + chordRouting.genKey(i));
//            System.out.println("search result: " + node.getNodeName());
//            System.out.println();
//        }


    }

    public Node search(int lastStudentNumber) {
        int key = genKey(lastStudentNumber);
        Node startNode = getStartNode(lastStudentNumber);

        System.out.println("Start search: " + startNode.getNodeName());
        if (key < startNode.getValue()) {
            // key小于开始节点值时，不能判定当前节点是否key的后继节点，需要从第一个节点开始
            System.out.println("Key value is lower than start node, than search from origin node: " + nodeList.get(0).getNodeName());
            return search(key, nodeList.get(0));
        } else {
            return search(key, startNode);
        }

    }

    private Node search(int key, Node node) {
        System.out.println("---- search node: " + node.getNodeName());

        if (key <= node.getValue()) {
            System.out.println("---- search success: " + node.getNodeName());
            return node;
        }

        Node successorNode = successor(node);
        if (key<=successorNode.getValue()) {
            System.out.println("---- search success: " + successorNode.getNodeName());
            return successorNode;
        }

        LinkedHashMap<Integer, Node> fingerTable = node.getFingerTable();
        List<Integer> indexFingerList = new ArrayList<>(fingerTable.keySet());
        // 从最远的后继节点开始比较
        for (int i = indexFingerList.size() - 1; i >= 0; i--) {
            int finger = indexFingerList.get(i);
            Node nodeTmp = fingerTable.get(finger);
            if (nodeTmp.getValue() > node.getValue() && nodeTmp.getValue() <= key) {
                return search(key, nodeTmp);
            }
        }

        return nodeList.get(0);
    }

    /**
     * 获取某一节点的后继节点
     * @param node
     * @return
     */
    public Node successor(Node node) {
        List<Integer> indexFingerList = new ArrayList<>(node.getFingerTable().keySet());
        return node.getFingerTable().get(indexFingerList.get(0));
    }

    public void init(int spaceSize, List<Integer> nodeValueList) {
        this.spaceSize = spaceSize;
        this.nodeList = new ArrayList<>();
        int maxValue = (int) Math.pow(2, spaceSize) - 1;
        for (Integer integer : nodeValueList) {
            if (integer > maxValue) {
                throw new IllegalArgumentException("space is not satisfied");
            }
            nodeList.add(new Node(integer));
        }

        for (Node node : nodeList) {
            genFingerTable(node);
        }

    }

    /**
     * 构建节点的FingerTable
     * @param node
     */
    public void genFingerTable(Node node) {
        int maxValue = (int) Math.pow(2, spaceSize) - 1;
        int value = node.getValue();
        LinkedHashMap<Integer, Node> table = new LinkedHashMap<>();
        for (int i = 1; i <= spaceSize; i++) {
            int indexAdd = (int) Math.pow(2, i - 1);
            int valueTmp = (value + indexAdd) % maxValue;
            boolean fix = false;
            for (Node nodeTmp : nodeList) {
                if (nodeTmp.getValue() >= valueTmp) {
                    table.put(indexAdd, nodeTmp);
                    fix = true;
                    break;
                }
            }
            if (!fix) {
                table.put(indexAdd, nodeList.get(0));
            }
        }

        node.setFingerTable(table);

        System.out.println(node);
    }

    public int genKey(int lastStudentNumber) {
        return 14 * lastStudentNumber + 67;
//        return 67 * lastStudentNumber + 14;
    }

    public Node getStartNode(int lastStudentNumber) {
        if (lastStudentNumber == 0) {
            lastStudentNumber = 10;
        }
        return getNodeByValue(NODE_VALUE_LIST.get(lastStudentNumber-1));
    }

    public Node getNodeByValue(int value) {
        for (Node node : nodeList) {
            if (node.getValue() == value) {
                return node;
            }
        }
        return null;
    }
}


